package cn.fxzhang.leetcode.no00;


/**
 * 87. 扰乱字符串
 * 类型：动态规划
 * 题解：dp[i][j][len] 表示从字符串 S 中 i 开始长度为 len 的字符串是否能变换为从字符串 T 中 j 开始长度为 len 的字符串
 * 时间复杂度：O(N^4)
 * 空间复杂度：O(N^3)
 *
 * 提交记录(1/1)：
 * 执行用时: 11 ms, 击败了19.77%
 * 内存消耗: 38.8 MB, 击败了18.04%
 *
 * 【困难】通过次数34,893提交次数70,658
 * @author 张晓帆
 * @date 2021/4/17
 */
public class P0087_Scramble_String {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if (n != m){
            return false;
        }

        boolean [][][] dp = new boolean[n][n][n+1];
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }

        for (int len=2; len<=n; len++){
            for (int i=0; i<=n-len; i++){
                for (int j=0; j<=n-len; j++){
                    for (int k=1; k<len; k++){
                        dp[i][j][len] = dp[i][j][len] || dp[i][j][k] && dp[i+k][j+k][len-k]
                                || dp[i][j+len-k][k] && dp[i+k][j][len-k];
                    }
                }
            }
        }

        return dp[0][0][n];
    }

}
